Service provenance data stored in relational database and document database cannot provide effective service tracking operations and graphic database storage cannot execute rapid aggregation operations. In order to solve the problems, a new service provenance tracking mechanism based on graph was proposed. On the basis of graphic database storage service provenance tracking mechanism, the service provenance storage structure in the graphic database was defined, and the aggregation operation for this storage structure was provided. Then the three different service provenance tracking models which were separately based on static weight, mixed operation and real-time task. The experimental results show that the proposed service provenance tracking mechanism can meet different query requirements of different types of service provenance data such as aggregation and tracking operation, reduces the service tracking time-consuming and improves the tracking efficiency of service provenance.